转自原文 深入理解空间搜索算法 ——数百万数据中的瞬时搜索

上图为全球138,000个热门地点的R-tree的可视化图示

我这个人沉迷于软件性能的提升，我在Mapbox（https://www.mapbox.com/）的职责之一就是找到能使我们的映射平台更加快速的方法。当面对大规模的空间数据时，一个最有效也是最重要的方法就是空间索引（https://en.wikipedia.org/wiki/Spatial_database#Spatial_index）。

空间索引是一系列可以通过排列几何数据来进行高效索引的算法。例如，查询“本区域所有的建筑”、“距此点最近的1000个加油站”等问题，查询结果往往能够在几毫秒内返回，即使所要查询的目标有几百万个。

空间索引是数据库如PostGIS的基础，同时也是我们平台的核心。在很多其他任务尤其是性能至关重要的任务中，空间索引也非常重要。特别的，在处理遥测数据时，我们需要对数百万个GPS样本与道路网进行匹配，以产生导航所用的实时交通数据。在客户端，我们则需要实时在地图中展示地标，以及在鼠标滞留时查找鼠标所指的目标。

在过去的四年里，我建立了一些快速的用于空间搜索的Java 库，包括：

rbush（https://github.com/mourner/rbush）,

rbush-knn（https://github.com/mourner/rbush-knn/）,

kdbush（https://github.com/mourner/kdbush）,

geokdbush（https://github.com/mourner/geokdbush）。